/*
 * HashTable.hpp
 *
 *  Created on: 2011-3-7
 *      Author: hao
 *
 *      Hashtable.
 */

#ifndef HASHTABLE_HPP_
#define HASHTABLE_HPP_

#include <string>

template<typename T>
struct HashCell {

	bool bSet;

	T data;

	HashCell<T> * pNext;

	int label;

	HashCell(T Data, int Label) {

		data = Data;
		bSet = true;
		label = Label;
		pNext = NULL;

	}

	HashCell() {

		data = T();
		bSet = false;
		label = 0;
		pNext = NULL;

	}

};

template<typename T>
class HashTable {

	int size;

	HashCell<T> * pData;

	T NoThingReturn;

	void CopyHashTable(const HashTable & t);

	void DeleteData();

public:

	HashTable(int Size = 20) :
		size(Size), NoThingReturn(T()) {

		pData = new HashCell<T> [size];

	}

	HashTable(const HashTable<T> & t);

	~HashTable();

	void Insert(int label, T data);

	void setNoThingReturn(T Return);

	HashTable<T> & operator=(const HashTable<T> & t);

	T operator[](int index);

};

template<typename T>
HashTable<T> & HashTable<T>::operator=(const HashTable<T> & t) {

	if (&t == this)
		return *this;

	DeleteData();

	CopyHashTable( t );

	return *this;

}

template<typename T>
HashTable<T>::HashTable(const HashTable<T> & t) {

	CopyHashTable(t);

}

template<typename T>
HashTable<T>::~HashTable() {

	DeleteData();

}

template<typename T>
void HashTable<T>::Insert(int label, T data) {

	int t = label;

	//除法散列法
	while (t >= size)
		t %= size;

	if (pData[t].bSet) {

		HashCell<T> * pEnd = pData + t;

		while (pEnd->pNext)
			pEnd = pEnd->pNext;

		pEnd->pNext = new HashCell<T> (data, label);

		return;

	} else {

		pData[t].data = data;

		pData[t].bSet = true;

		pData[t].label = label;

		return;

	}

}

template<typename T>
T HashTable<T>::operator [](int index) {

	if( index < 0 ) return NoThingReturn;

	int label = index;

	while (index >= size)
		index %= size;

	if (pData[index].bSet) {

		HashCell<T> * pNode = pData + index;

		while (pNode && pNode->label != label)
			pNode = pNode->pNext;

		if (pNode)
			return pNode->data;
		else
			return NoThingReturn;

	} else
		return NoThingReturn;

}

template<typename T>
void HashTable<T>::setNoThingReturn(T Return) {

	NoThingReturn = Return;

}

template<typename T>
void HashTable<T>::CopyHashTable(const HashTable & t) {

	pData = new HashCell<T> [t.size];

	size = t.size;

	NoThingReturn = t.NoThingReturn;

	{
		HashCell<T> * pLast;
		HashCell<T> * pCurrentCell; //复制t的当前Cell
		for (int i = 0; i < size; i++) {

			pData[i] = t.pData[i];

			pLast = pData + i;

			pCurrentCell = t.pData[i].pNext;

			while (pCurrentCell) {

				pLast->pNext = new HashCell<T> (*pCurrentCell);

				pCurrentCell = pCurrentCell->pNext;

			}

		}
	}

}

template<typename T>
void HashTable<T>::DeleteData() {
	if (pData) {

		HashCell<T> * pCell;

		HashCell<T> * pTemp;

		//删除每个Hash元素的外接表
		for (int i = 0; i < size; i++) {

			pCell = pData[i].pNext;

			while (pCell) {

				pTemp = pCell;

				pCell = pCell->pNext;

				delete pTemp;

			}

		}

		//删除hash
		delete[] pData;

		pData = NULL;

	}

}

#endif /* HASHTABLE_HPP_ */
